The “traveling salesman” problem is a well-known in optimization theory. The problem may be expressed as determining the shortest path that will allow a salesman to visit all the cities on a map and return to his starting position. While many straightforward, brute-force solutions to this problem are known, all suffer from the defect that the computational complexity increases exponentially as a function of the number of cities.
The traveling salesman problem is among the most thoroughly investigated problems in the field of optimization theory. It serves as a benchmark test where optimization algorithms compete for world records. Many algorithms have been developed to solve this problem, but no general solution has yet been proposed which can find the best path that scales polynomially with the number of cities. Many suppose that there is no general solution which can find the best path that scales polynomially with the number of cities.
Additional information on the history and background of the traveling salesman problem can be found in published materials including G. Gutin & ed. A. P. Punnen, ed., The Traveling Salesman Problem and Its Variations (Kluwer Academic Publishers, 2002) and E. L. Lawler, J. K. Lenstra, A. H. G. Rinnooy Kan, & D. B. Shmoys, eds., The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (John Wiley & Sons, 1985).
Applying techniques of statistical physics, applicant has invented a process which provides a general solution to the traveling salesman problem, wherein said process scales polynomially with the number of cities. In addition, the solution finds all solutions not just one. The approach is a statistical physics approach which determines the distribution of all solutions. Previous attempts of applying statistical physics have failed at determining a general solution because they could not rule out all un-allowed paths. In one embodiment, the present invention relies in part on a description of the solution distribution capable of excluding all unallowed paths.